package cn.xkai.exercise.b;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;

/**
 * @description: 克隆图
 * @author: kaixiang
 * @date: 2022-07-21
 **/
public class Solution81 {
    public Node cloneGraph(Node node) {
        return clone(node, new HashMap<>(8));
    }

    public Node clone(Node node, HashMap<Integer, Node> visited) {
        //边界条件判断
        if (node == null)
            return null;
        //如果当前节点已经创建了，直接返回
        if (visited.containsKey(node.val))
            return visited.get(node.val);
        //否则创建当前节点
        Node newNode = new Node(node.val, new ArrayList<>());
        //把创建的节点存放到map中
        visited.put(newNode.val, newNode);
        //创建当前节点的邻居节点
        for (Node neighbor : node.neighbors)
            newNode.neighbors.add(clone(neighbor, visited));
        return newNode;
    }

    static class Node {
        public int val;
        public List<Node> neighbors;

        public Node() {
            val = 0;
            neighbors = new ArrayList<Node>();
        }

        public Node(int _val) {
            val = _val;
            neighbors = new ArrayList<Node>();
        }

        public Node(int _val, ArrayList<Node> _neighbors) {
            val = _val;
            neighbors = _neighbors;
        }
    }
}
